package ai.zixing.mashibing.basic_class.class11;

/**
 * N皇后
 *
 * N皇后问题是指在N*N的棋盘上要摆N个皇后，
 * 要求任何两个皇后不同行、不同列， 也不在同一条斜线上
 * 给定一个整数n，返回n皇后的摆法有多少种。n=1，返回1
 * n=2或3，2皇后和3皇后问题无论怎么摆都不行，返回0
 * n=8，返回92
 *
 *
 * O(N^N)
 * 位运算只是加速了常数项问题
 */
public class Code09_NQueens {

    public static int num1(int n) {
        if (n < 1) {
            return 0;
        }
        // record[i] : i 行的皇后放在了第几列
        int[] record = new int[n];
        return process1(0, record, n);
    }

    // 潜台词：record[0..i-1]的皇后，任何两个皇后一定都不共行、不共列，不共斜线
    // 目前来到了第i行
    // record[0..i-1]表示之前的行，放了的皇后位置
    // n代表整体一共有多少行 0 ~ n-1 才是有效的
    // 返回值是，摆完所有的皇后，合理的摆法有多少种
    public static int process1(int i, int[] record, int n) {
        // 终止行
        if (i == n) {
            return 1;
        }
        // 没有终止，还有皇后要摆
        int res = 0;
        // 当前行在i行，尝试i行所有的列  -> j
        for (int j = 0; j < n; j++) {
            if (isValid((record), i, j)) {
                // 不用还原现场
                record[i] = j;
                res += process1(i + 1, record, n);
            }
        }
        return res;
    }

    // 返回 i 行皇后，放在 j 列是否有效
    public static boolean isValid(int[] record, int i, int j) {
        for (int k = 0; k < i; k++) {
            // j == record[k] 同列
            // Math.abs(record[k] - j) == Math.abs(i - k) 同斜线
            // (k, record[k]) (i, j)
            if (j == record[k] || Math.abs(record[k] - j) == Math.abs(i - k)) {
                return false;
            }
        }
        return true;
    }


    // 不超过 32 皇后
    public static int num2(int n) {
        if (n < 1 || n > 32) {
            return 0;
        }
        // limit 表示 N 皇后，则 最后 N 位是 1， 其他位是 0
        int limit = n == 32 ? -1 : (1 << n) - 1;
        return process2(limit, 0, 0, 0);
    }

    // limit 划定问题的规模，固定不变
    // colLim 列的限制，1的位置不能放皇后，0的位置可以
    // leftDiaLim 左斜线的限制，1的位置不能放皇后，0的位置可以
    // rightDiaLim 右斜线的限制，1的位置不能放皇后，0的位置可以
    public static int process2(int limit, int colLim, int leftDiaLim, int rightDiaLim) {
        // 试完了，前面着一种情况 base case
        if (colLim == limit) {
            return 1;
        }
        // colLim | limit | rightDiaLim 表示总限制
        // ~(colLim | limit | rightDiaLim) 可以摆皇后的位置
        // limit & (~(colLim | limit | rightDiaLim)) 将左侧出棋盘的 1 去掉了
        // 所有可以放皇后的位置，都在 pos 上
        int pos = limit & (~(colLim | leftDiaLim | rightDiaLim));
        int mostRightOne = 0;
        int res = 0;
        while (pos != 0) {
            // 提取出 pot 中，最右侧的 1
            // 即 while 是在 1 的位置上循环
            mostRightOne = pos & (~pos + 1);
            // pos 的倒数第二个 1 ，即下次循环的位置
            pos = pos - mostRightOne;
            res += process2(limit,
                    // 列限制
                    colLim | mostRightOne,
                    // 左限制
                    (leftDiaLim | mostRightOne) << 1,
                    // 右限制
                    (rightDiaLim | mostRightOne) >>> 1);
        }
        return res;
    }

    public static void main(String[] args) {
        int n = 14;
        long start = System.currentTimeMillis();
        System.out.println(num2(n));
        long end = System.currentTimeMillis();
        System.out.println("cost time: " + (end - start) + "ms");

        start = System.currentTimeMillis();
        System.out.println(num1(n));
        end = System.currentTimeMillis();
        System.out.println("cost time: " + (end - start) + "ms");
    }

}
